home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / c_toolbx.arc / BT_DEL.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-30  |  4.4 KB  |  141 lines
  1. /*  bt_del.c - delete function */
  2. #include   "stdio.h"
  3. #include   "btree.h"
  4. #include   "bt_macro.h"
  5. extern    IX_DESC    *pci ;
  6. extern    int  split_size ;
  7. extern    int  comb_size ;
  8. BLOCK    *neighbor() ;
  9.  
  10. int  delete_ix(pix)            /* delete current entry */
  11.   IX_DESC  *pix ;            /* points to index descriptor */
  12.   {                    /* returns success=1 , failure=0 */
  13.      ENTRY tempe ;
  14.      BLOCK b ;
  15.      int   ret ;
  16.  
  17.      pci = pix ;
  18.                 /* check for dummy entry at end-of-ix */
  19.      copy_curreny(0,&tempe) ;
  20.      if( call(pci->pcomp)(&tempe,& pci->dx.dume) == 0 )
  21.     return( IX_FAIL ) ;
  22.                     /* not at end - delete it  */
  23.      ret = del_level(0,&b) ;
  24.  
  25.      return( ret ) ;
  26.   }
  27.  
  28.  
  29. int  del_level(l,pb)            /* delete entry within the level */
  30.   int    l ;
  31.   BLOCK *pb ;
  32.   {
  33.      RECPOS   r ;
  34.      int   ret    ;
  35.      ENTRY tempe ;
  36.  
  37.      ret = IX_OK ;
  38.      retrieve_block(l,CB(l),pb,CURR) ;    /* get current block */
  39.      del_block(pb,CO(l)) ;        /* delete the entry in the block */
  40.  
  41.      if( pb->bend == 0 )        /* block now empty ? */
  42.     {  put_free(pb) ;        /* yes - free the block */
  43.        ret = del_level(l+1,pb) ;    /* delete entry for empty block */
  44.        copy_current(l+1,&tempe) ;    /* get new current block pointer */
  45.        first_ix(l,pb,tempe.rptr) ;    /* reset pos for lower levels */
  46.        return( ret ) ;
  47.     }
  48.      if( CO(l) >= pb->bend )        /* last entry in block deleted ? */
  49.     {                /* yes - correct upper index */
  50.        fix_last(l,pb->brec,ENT_ADR(pb,last_entry(pb))) ;
  51.     }
  52.      if(   pb->bend < comb_size)    /* less than half full ? */
  53.     ret + compress(l,pb) ;        /* yes - try combine with neighbor */
  54.      else  update_block(pb) ;
  55.      retrieve_block(l,CB(l),pb,CURR) ;    /* get our block again */
  56.      if(CO(l) >= pb->bend )        /* is position past end of block ? */
  57.     first_ix(l,pb,next_ix(l+1)) ;    /* yes - move to next block */
  58.      return( ret ) ;
  59.   }
  60.  
  61.  
  62. int  compress(l,pb)            /* combine a block with a neighbor */
  63.   int l ;
  64.   BLOCK *pb ;                /* the block to be combined */
  65.   {
  66.      int   nb ;
  67.      BLOCK *pt ;
  68.      ENTRY tempe ;
  69.  
  70.  
  71.      if( (l+1) == pci->dx.nl )        /* is this the root level ? */
  72.     {  update_block(pb) ;        /* yes - update the block */
  73.        return( IX_OK ) ;        /* and return */
  74.     }
  75.  
  76.      pt = neighbor(l,LEFTN) ;        /* get left neighbor block */
  77.      if(   (pt != NULL )
  78.     && (pt->bend + pb->bend <= IXB_SPACE)  )
  79.     {  combine(pt,pb) ;        /* combine blocks */
  80.        update_block(pb) ;        /* update right block */
  81.        put_free(pt) ;        /* free the left index block */
  82.                     /* CB(l) is ok as is */
  83.        CO(l) = CO(l) + pt->bend ;    /*  adjust our current pos. */
  84.        last_ix(l+1,pb) ;        /* point higher level to left blk */
  85.        del_level(l+1,pb) ;        /* delete ptr. tp left block */
  86.        return( IX_OK ) ;
  87.     }
  88.  
  89.  
  90.      pt = neighbor(l,RIGHTN) ;        /* get right neighbor block */
  91.      if(   (pt != NULL )
  92.     && (pt->bend + pb->bend <= IXB_SPACE)  )
  93.     {  combine(pb,pt) ;        /* combine blocks */
  94.        update_block(pt) ;        /* update right block */
  95.        CB(l) = pt->brec ;        /* right block is curr. one now */
  96.                     /* CO(l) is ok as is */
  97.        put_free(pb) ;        /* free the left index block */
  98.        del_level(l+1,pb) ;        /* delete ptr. tp left block */
  99.        return( IX_OK ) ;
  100.     }
  101.  
  102.      update_block(pb) ;         /* can't combine - just update blk. */
  103.      return( IX_OK ) ;
  104.   }
  105.  
  106. int  fix_last(l,r,pe)            /* fix higher level index */
  107.   int    l ;                /* level we are on */
  108.   RECPOS   r ;                /* rptr for higher level entry */
  109.   ENTRY *pe ;                /* entry with new key */
  110.   {
  111.      ENTRY tempe ;
  112.                 /* last entry in a block deleted/replaced */
  113.                 /* update higher level index */
  114.  
  115.      copy_entry(&tempe,pe) ;        /* copy key */
  116.      tempe.rptr = r ;            /* put in the record pointer */
  117.      return( replaced_entry(l+1,&tempe) ) ; /* replace the entry */
  118.   }
  119.  
  120.  
  121. int  replace_entry(l,pe)        /* replace current index entry */
  122.   int    l ;                /* at this index level */
  123.   ENTRY *pe ;                /* new entry */
  124.   {
  125.      BLOCK b ;
  126.      int   ret ;
  127.  
  128.      retrieve_block(l,CB(l),&b,CURR) ;    /* get the index block */
  129.      if( CO(l) == last_entry(&b))    /* is this the last entry ? */
  130.     fix_last(l,CB(l),pe) ;        /* yes - fix up higher level */
  131.      del_block(&b,CO(l)) ;        /* remove the current entry */
  132.                     /* room to insert the new entry */
  133.      if( (b.bend + ENT_SIZE(pe)) <= split_size )
  134.     {  ins_block(&b,pe,CO(l)) ;    /* yes - insert in the block */
  135.        update_block(&b) ;        /*    and update the block */
  136.        ret = IX_OK ;
  137.     }
  138.      else ret = split(l,pe,&b) ;    /* no - split the block */
  139.      return( ret ) ;
  140.   }
  141.